package sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

/**
 * 基数排序可以理解为"计数"排序的基础之上的 一种排序算法
 * 8w 数据耗时0.067s
 * 还有个问题就是 出现负数的情况，1）我认为再多10个桶。（太浪费空间）
 *                             2）所有数加上min的绝对值，排序完后再减去它（注意越界问题）
 * 还有个问题就是内存占用十分恐怖 ： 我们11个数组，每个数组800万，Integer 4字节
 *  8000000 * 11 * 4 /1024 / 1024 /1024 ~= 3G
 */
public class RadixSorting {
    public static void main(String[] args) {
        /**
         * 处理有负数的情况
         */
        int[] arr = {-888,2, 3, 6, 1, 7, 4, 34, -67,999};
        int min = Math.abs(getMin(arr));
        for (int i = 0; i < arr.length; i++) {
            arr[i]+=min;
        }
        radix(arr);
        System.out.println(Arrays.toString(arr));
        for (int i = 0; i < arr.length; i++) {
            arr[i]-=min;
        }
        for (int i : arr) {
            System.out.printf(i+" ");
        }
        int[] arr2 = {888,2, 3, 6, 1, 7, 4, 34, 67,999};
        radix(arr2);
        System.out.println(Arrays.toString(arr2));
        //costTime();
    }

    public static void radix(int[] arr) {
        int maxLength = getMaxNumDigit(arr);
        System.out.println("这个数组里最大值长度位"+maxLength);
        // 创建二维数组，并初始化默认capacity为10
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            buckets.add(new ArrayList<>());
        }
        for (int j = 0; j < maxLength; j++) {
            // 第一轮将个位数映射到数组里面
            for (int i = 0; i < arr.length; i++) {
                /**
                 * 如果是个位 /1%10
                 * 如果是10位 /10%10
                 * 如果是100位 /100%10
                 */
                int digit = (int) (arr[i] / Math.pow(10,j) % 10);
                buckets.get(digit).add(arr[i]);
            }
            // 将桶里面的值放回数组
            bucketToArray(arr, buckets);
           System.out.println("第"+(j+1)+"次基数排序"+ Arrays.toString(arr));
        }
    }

    /**
     * 将桶中的元素赋值给数组，并把桶清空。我卡在了清空桶的操作上....反正也是空间换时间..谁不是换呢    <3
     */
    public static void bucketToArray(int[] arr, ArrayList<ArrayList<Integer>> bucketArr) {
        int index = 0;
        for (int i = 0; i < bucketArr.size(); i++) {
            int temp = bucketArr.get(i).size();
            for (int j = 0; j < temp; j++) {
                arr[index++] = bucketArr.get(i).get(j);
            }
            // 清空桶 ... 感觉这步有点耗时间 n个数据需要n次清空
            for (int j = temp - 1; j >= 0; j--) {
                bucketArr.get(i).remove(j);
            }
        }
    }
    /**
     * 获得一个数组里面最大数的长度
     */
    private static int getMaxNumDigit(int[]arr){
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
            max = Math.max(max,i);
        }
        return (""+max).length();
    }
    private static int getMin(int[] arr){
        int min = Integer.MAX_VALUE;
        for (int i : arr) {
            min = Math.min(min,i);
        }
        return min;
    }

    /**
     *  测试八万的数据
     */
    public static void costTime() {
        int[] arrays3 = new int[8000000];
        Random random2 = new Random();
        for (int i = 0; i < arrays3.length; i++) {
            arrays3[i] = random2.nextInt(8000000);
        }
        long startTime = System.currentTimeMillis();
        radix(arrays3);   // 正规的插入，有值的后移
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间优化时间为：" + (endTime - startTime)*0.001 + "s"); //输出程序运行时间
    }
}
